package solution.s_4;


/**
 * 解题思路
 *
 * 先判断特殊情况
 * 1. nums1 和 nums2 两个都为空，直接返回0；
 * 2. 假如其中一个为空，例如 nums1 为空，就判断 nums2 的长度。假如 nums2 的长度为奇数，返回最中间的那个数据；假如长度为偶数，返回中间那两个数据的和除以2的数值。
 *
 * 最常见的情况（两个数组都不为空）
 * 1. 从想法上将 2 个数组合并为一个数据，还是一样的做法，假如长度为奇数，返回中间的那个数值；假如长度为偶数，返回中间的两个数值之和除以 2 的数值。
 * 2. 接下来使用 2 个指针记录 2 个数组遍历到的位置，直到遍历到需要计算中位数的位置。
 * 3. 将数值相加除以2。此处为了方便处理，都以 2 个数值进行处理，假如长度为奇数，中间数字是 5，那么计算中位数的时候也是使用 (5+5)/2 进行计算。
 */
public class Solution20220215 {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;

        if (0 == len1 && 0 == len2) {
            return 0;
        }
        if (0 == len1) {
            return len2 % 2 == 1 ? nums2[len2/2] : ((nums2[len2/2-1] + nums2[len2/2]) / 2.0);
        }
        if (0 == len2) {
            return len1 % 2 == 1 ? nums1[len1/2] : ((nums1[len1/2-1] + nums1[len1/2]) / 2.0);
        }

        // 中位数位置
        int num1Index, num2Index;
        // 两个中位数
        int num1 = 0, num2 = 0;
        // 两个数组的两个指针
        int p1 = 0, p2 = 0;
        // 记录遍历的数量
        int s = 0;

        int lenT = len1 + len2;
        if (lenT % 2 == 0) {
            num1Index = lenT / 2;
            num2Index = lenT / 2 + 1;
        } else {
            num1Index = num2Index = lenT / 2 + 1;
        }

        while (s < num2Index) {
            int cur;
            if (p1 >= len1) {
                cur = nums2[p2];
                p2 ++;
            } else if (p2 >= len2) {
                cur = nums1[p1];
                p1 ++;
            } else {
                if (nums1[p1] <= nums2[p2]) {
                    cur = nums1[p1];
                    p1 ++;
                } else {
                    cur = nums2[p2];
                    p2 ++;
                }
            }
            s ++;

            if (s == num1Index) { num1 = cur; }
            if (s == num2Index) { num2 = cur; }
        }

        return (num1 + num2) / 2.0;
    }

}
